/**
 *  @file dfs_d.c
 *  @brief depth-first search for directed graphs, using the
 *	        detailed algorithm of Cormen, Leiserson, and Rivest
 *         (Introduction to Algorithms, first edition, p. 478)
 * @author Matt Stallmann
 * @date 1991
 * <br>$Id: dfs_d.c 10 2007-06-28 20:08:57Z mfms $
 */

/*
 *  Copyright (C) 1991  Matthias Stallmann.
 *  Contact: matt_stallmann@ncsu.edu
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program (file COPYING.txt); if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  USA.
 */

#include <stdio.h>
#include "Gdr.h"

short color[MAX_VERTEX]; /* WHITE if unvisited, GRAY if on stack, BLACK
							       if finished visit */
#define WHITE 0
#define GRAY 1
#define BLACK 2

int d[MAX_VERTEX]; /* time that vertex is discovered (preorder number) */
int f[MAX_VERTEX]; /* time that visit is finished (postorder number) */
int time_stamp; 	 /* current time stamp */

 /* declarations and macros for the animation */
#define MSG_SIZE 100 /* maximum length of a message */
char msg[MSG_SIZE];
TWIN pwin; /* window for user prompts */
#define XW 1        /* prompt window coordinates */
#define YW 1
#define init_prompt_window (pwin = create_text_window(XW,YW,""))
#define destroy_prompt_window (kill_window(pwin))
#define wait(msg) (write_text_window(pwin,msg),suspend_animation(),\
				   hide_window(pwin))
#define COUNT 4

void DFS_Visit(vertex u)
{
  vertex v; /* current other vertex in adjacency list */
  edge e; /* current edge in adjacency list */

  color[u] = GRAY;
  d[u] = time_stamp = time_stamp + 1;

  expose_vertex_label(u);
  sprintf(msg,"%d/",d[u]);
  change_vertex_label(u,msg);
  sprintf(msg,"Start visit, vertex %d\nClick Resume to continue",u);
  wait(msg);

  for_adjacent(u,e,v) {
	blink_edge(e,COUNT);
	if (color[v] == WHITE) { /* tree edge */
	  hide_edge_label(e);
	  highlight_edge(e);
	  DFS_Visit(v);
	}
	else if (color[v] == GRAY) { /* back edge */
	  expose_edge_label(e);
	  change_edge_label(e,"B");
	}
	else if (d[u] < d[v]) {	/* forward edge */
      expose_edge_label(e);
      change_edge_label(e,"F");
	}
	else { /* d[u] > d[v] -- cross edge */
      expose_edge_label(e);
      change_edge_label(e,"C");
	}
  }
  color[u] = BLACK;
  f[u] = time_stamp = time_stamp + 1;

  un_highlight_vertex(u);
  sprintf(msg,"%d/%d",d[u],f[u]);
  change_vertex_label(u,msg);

  sprintf(msg,"End visit, vertex %d\nClick Resume to continue",u);
  wait(msg);
}

void DFS(void)
{
  vertex u;
  edge e;

  /* initialize the animation */
  for_all_vertices(u) {
    highlight_vertex(u);
    hide_vertex_label(u);
  }
  for_all_edges(e) {
    hide_edge_label(e);
  }
  init_prompt_window;

  for_all_vertices(u) {
    color[u] = WHITE;
  }

  time_stamp = 0;
  write_text_window(pwin,"Select vertex for starting DFS\ntype `q` to quit");
  while ((u = select_vertex()) != NULL_VERTEX) {
    if (color[u] == WHITE) {
      DFS_Visit(u);
      write_text_window(pwin,"Select another starting vertex\ntype `q` to quit");
    }
    else {
      hide_window(pwin);
      write_text_window(pwin,"Vertex already visited, try again");
    }
  }
  wait("End of depth-first search\nClick RESUME to exit animation");
  for_all_vertices(u) {
    change_vertex_label(u,"");
    hide_vertex_label(u);
    un_highlight_vertex(u);
  }
  for_all_edges(e) {
    change_edge_label(e,"");
    expose_edge_label(e);
    un_highlight_edge(e);
  }
  destroy_prompt_window;
}

void animat(void) {DFS();}

/*  [Last modified: 2007 06 28 at 19:44:15 GMT] */
